package com.study.leetcode;

public class _79 {
    public boolean exist(char[][] board, String word) {
        int[][] ints = new int[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                boolean b = find(board, word, 0, i, j, new int[board.length][board[i].length]);
                if (b) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean find(char[][] board, String word, int index, int m, int n, int[][] cache) {
        if (m < 0 || n < 0 || m >= board.length || n >= board[0].length || board[m][n] != word.charAt(index) || cache[m][n] == 1) {
            return false;
        }
        if (board[m][n] == word.charAt(index) && index == word.length() - 1) {
            return true;
        }
        cache[m][n] = 1;
        if (find(board, word, index + 1, m + 1, n, cache)
                || find(board, word, index + 1, m - 1, n, cache)
                || find(board, word, index + 1, m, n + 1, cache)
                || find(board, word, index + 1, m, n - 1, cache)) {
            return true;
        }
        cache[m][n] = 0;
        return false;
    }

    public static void main(String[] args) {
        _79 v = new _79();
        System.out.println(v.exist(new char[][]{
                {'A','B','C','E'},
                {'S','F','C','S'},
                {'A','D','E','E'}}, "SEE"));
    }
}
